package com.stefan.linkedlist;


//循环链表 + 尾插法
public class StefanCircleLinkedList<E> {
    private int size;
    private Node<E> head;
    private Node<E> tail;
    public StefanCircleLinkedList() {
        this.size = 0;
        this.head = null;
        this.tail = null;
    }

    static class Node<E> {
        private E data;
        private Node<E> next;
        public Node(E data) {
            this.data = data;
            this.next = null; // 初始化时指向null
        }
    }

    public void add (E data) {
        Node<E> node = new Node(data);
        if (size == 0) {
            head = node;
            tail = node; // 初始化时，头和尾都指向同一个节点
            node.next = head; // 形成循环
            size++;
        } else {
            //非空链表
            tail.next = node; // 将新节点添加到尾部
            node.next = head; // 新节点指向头节点，形成循环
            tail = node; // 更新尾节点
            size++;
        }
    }

    public boolean remove(E data) {
        if (size == 0) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> current = head;
        Node<E> prev = tail;

        do {
            if (current.data.equals(data)) {
                if (current == head) {
                    head = head.next; //删除header
                    tail.next = head;
                } else if (current == tail) {
                    tail = prev;
                    tail.next = head;
                } else {
                    prev.next = current.next;
                }
                size--;
                return true;
            }
            prev = current;
            current = current.next;
        } while (current != head);
        return false;
    }
    public void print() {
        Node<E> var = this.head;
        for (int i = 0; i < size; i++) {
            System.out.print(var.data + "");
            var = var.next;
        }
        System.out.println("");
    }

    //约瑟夫问题
    public void josephus(int m) {
        if (m <= 0 || size == 0) {
            throw new IllegalArgumentException("Invalid input");
        }
        Node<E> current = this.head;
        while (size > 1) {
            for (int i = 0; i < m-1; i++) {
                current = current.next; // 找到要删除的节点
            }
            System.out.println("Removing: " + current.data);
            remove(current.data); // 删除节点
            current = current.next; // 移动到下一个节点
        }
    }


    public static void main(String[] args) {
        StefanCircleLinkedList<Integer> stefanLinkedList = new StefanCircleLinkedList();
        stefanLinkedList.add(1);
        stefanLinkedList.add(2);
        stefanLinkedList.add(3);
        stefanLinkedList.add(4);
        stefanLinkedList.add(5);
        stefanLinkedList.add(6);
        stefanLinkedList.add(7);
        stefanLinkedList.add(8);
        stefanLinkedList.add(9);

        stefanLinkedList.josephus(5);
//        boolean remove = stefanLinkedList.remove(8);
        System.out.println("Current List:"+stefanLinkedList.size);
    }
}
